from nfa import *

class Pattern:
    def bracket(self, outer_precedence):
        if self.precedence() < outer_precedence:
            return '(' + str(self) + ')'
        else:
            return str(self)
        
    def matches(self, string):
        return self.to_nfa_design().accepts(string)

    def __repr__(self):
        return f"/{str(self)}/"

    def precedence(self):
        raise NotImplementedError("Subclass must implement the precedence method")

    def __str__(self):
        raise NotImplementedError("Subclass must implement the __str__ method")
        
class Empty(Pattern):
    def __str__(self):
        return ''

    def precedence(self):
        return 3
    
    def to_nfa_design(self):
        start_state = object()
        accept_states = [start_state]
        rulebook = NFARulebook([])
        return NFADesign(start_state, accept_states, rulebook)
    
class Literal(Pattern):
    def __init__(self, character):
        self.character = character

    def __str__(self):
        return self.character

    def precedence(self):
        return 3
    
    def to_nfa_design(self):
        start_state = object()
        accept_state = object()
        rule = FARule(start_state, self.character, accept_state)
        rulebook = NFARulebook([rule])
        return NFADesign(start_state, {accept_state}, rulebook)
    

class Concatenate(Pattern):
    def __init__(self, first, second):
        self.first = first
        self.second = second

    def to_nfa_design(self):
        first_nfa_design = self.first.to_nfa_design()
        second_nfa_design = self.second.to_nfa_design()
        start_state = first_nfa_design.start_state
        accept_states = second_nfa_design.accept_states
        rules = first_nfa_design.rulebook.rules + second_nfa_design.rulebook.rules
        extra_rules = []
        for state in first_nfa_design.accept_states:
            rule = FARule(state, None, second_nfa_design.start_state)
            extra_rules.append(rule)
        rulebook = NFARulebook(rules+extra_rules)
        return NFADesign(start_state, accept_states, rulebook)

    def __str__(self):
        return "".join([self.first.bracket(self.precedence()), self.second.bracket(self.precedence())])

    def precedence(self):
        return 1
    
class Choose(Pattern):
    def __init__(self, first, second):
        self.first = first
        self.second = second

    def __str__(self):
        return "|".join([self.first.bracket(self.precedence()), self.second.bracket(self.precedence())])

    def precedence(self):
        return 0
    
    def to_nfa_design(self):
        first_nfa_design = self.first.to_nfa_design()
        second_nfa_design = self.second.to_nfa_design()
        start_state = object()

        #合并可接受状态
        accept_states = []
        accept_states.extend(first_nfa_design.accept_states)
        accept_states.extend(second_nfa_design.accept_states)

        #合并规则集
        rules = []
        rules.extend(first_nfa_design.rulebook.rules)
        rules.extend(second_nfa_design.rulebook.rules)

        #创建额外的自由移动规则
        extra_rules = []
        for nfa_desgin in [first_nfa_design, second_nfa_design]:
            rule = FARule(start_state, None, nfa_desgin.start_state)
            extra_rules.append(rule)

        # 合并所有规则
        all_rules = rules + extra_rules

        rulebook = NFARulebook(all_rules)

        return NFADesign(start_state, accept_states, rulebook)
    
class Repeat(Pattern):
    def __init__(self, pattern):
        self.pattern = pattern

    def __str__(self):
        return self.pattern.bracket(self.precedence()) + '*'

    def precedence(self):
        return 2
    
    def to_nfa_design(self):
        pattern_nfa_design = self.pattern.to_nfa_design()

        start_state = object()

        # 合并接收状态
        accept_states = []
        accept_states.extend(pattern_nfa_design.accept_states)
        accept_states.append(start_state)

        # 拷贝原有规则
        rules = []
        rules.extend(pattern_nfa_design.rulebook.rules)

        # 创建额外的自由移动规则
        extra_rules = []

        for accept_state in pattern_nfa_design.accept_states:
            rule = FARule(accept_state, None, pattern_nfa_design.start_state)
            extra_rules.append(rule)

        # 添加从新的起始状态到原起始状态的自由移动规则
        extra_rules.append(FARule(start_state, None, pattern_nfa_design.start_state))

        all_rules = rules + extra_rules
        rulebook = NFARulebook(all_rules)

        return NFADesign(start_state, accept_states, rulebook)
    

if __name__ == "__main__":
    # pattern = Repeat(
    #     Choose(
    #         Concatenate(Literal('a'),Literal('b')),
    #         Literal('a')
    #     )
    # )
    # print(pattern)

    # 测试空字符正则表达式的等价NFA转换
    nfa_design = Empty().to_nfa_design()
    # print(nfa_design)
    # print(nfa_design.accepts(''))
    # print(nfa_design.accepts('a'))
    # print(Empty().matches(''))
    # print(Empty().matches('a'))


    # 测试单字符正则表达式的等价NFA转换
    # nfa_design = Literal('a').to_nfa_design()
    # print(nfa_design.accepts(''))
    # print(nfa_design.accepts('a'))
    # print(nfa_design.accepts('b'))
    # print(Literal('a').matches(''))
    # print(Literal('a').matches('a'))
    # print(Literal('a').matches('b'))
    
    # 测试拼接正则表达式的等价NFA转换
    # pattern = Concatenate(Literal('a'), Literal('b'))
    # print(pattern.matches('a'))
    # print(pattern.matches('ab'))
    # print(pattern.matches('abc'))

    # pattern = Concatenate(
    #     Literal('a'),
    #     Concatenate(
    #         Literal('b'), Literal('c')
    #     )
    # )
    # print(pattern.matches('a'))
    # print(pattern.matches('ab'))
    # print(pattern.matches('abc'))

    # 测试选择正则表达式的等价NFA转换
    # pattern = Choose(Literal('a'), Literal('b'))
    # print(pattern)
    # print(pattern.matches('a'))
    # print(pattern.matches('b'))
    # print(pattern.matches('c'))

    # 测试Repeat正则表达式的等价NFA转换
    # pattern = Repeat(Literal('a'))
    # print(pattern)
    # print(pattern.matches(''))
    # print(pattern.matches('a'))
    # print(pattern.matches('aaaaa'))
    # print(pattern.matches('b'))

    # 综合测试正则表达式的等价NFA转换
    # pattern = Repeat(
    #     Concatenate(
    #         Literal('a'),
    #         Choose(
    #             Empty(),
    #             Literal('b')
    #         )
    #     )
    # )
    # print(pattern)
    # print(pattern.matches(''))
    # print(pattern.matches('a'))
    # print(pattern.matches('ab'))
    # print(pattern.matches('aba'))
    # print(pattern.matches('abab'))
    # print(pattern.matches('abaab'))
    # print(pattern.matches('abba'))
